package my.jwds.p94;

import java.util.ArrayList;
import java.util.List;

public class TreeNode {

    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static TreeNode to_searchBinary(int [] vals){
        TreeNode tree = new TreeNode(vals[0]);
        for (int i = 1; i < vals.length; i++) {
            TreeNode temp = tree;
            int val = vals[i];
            while(true){
                if (temp.val < val){
                    if (temp.right == null){
                        temp.right = new TreeNode(val);
                        break;
                    }
                    temp = temp.right;
                }else{
                    if (temp.left == null){
                        temp.left = new TreeNode(val);
                        break;
                    }
                    temp = temp.left;
                }
            }
        }
        return tree;
    }

    public static TreeNode to_binary(int [] vals){
        TreeNode[] treeNodes = new TreeNode[vals.length];
        for (int i = 0; i < vals.length; i++) {
            treeNodes[i] = new TreeNode(vals[i]);
        }
        int tier = (int) Math.ceil(Math.log(vals.length)/Math.log(2));
        for (int i = tier; i > 1; i--) {
            int tierNumber = Math.pow(2,i)-1 > vals.length?vals.length: (int) (Math.pow(2, i) - 1);
            int prevTierNumber = (int) (Math.pow(2,i-1)-1);
            while(prevTierNumber < tierNumber){
                if (treeNodes[prevTierNumber] != null){
                    if (prevTierNumber % 2 == 1){
                        treeNodes[prevTierNumber/2].left = treeNodes[prevTierNumber];
                    }else{
                        treeNodes[prevTierNumber/2-1].right = treeNodes[prevTierNumber];
                    }
                }
                prevTierNumber++;
            }
        }
        return treeNodes[0];
    }

    /**
     * 层序转换树，可以为空
     * @param vals
     * @return
     */
    public static TreeNode to_binaryHaveNull(Integer [] vals){
        TreeNode[] treeNodes = new TreeNode[vals.length];
        for (int i = 0; i < vals.length; i++) {
            if (vals[i] != null){
                treeNodes[i] = new TreeNode(vals[i]);
            }
        }
        int tier = (int) Math.floor(Math.log(vals.length)/Math.log(2))+1;
        for (int i = tier; i > 1; i--) {
            int tierNumber = Math.pow(2,i)-1 > vals.length?vals.length: (int) (Math.pow(2, i) - 1);
            int prevTierNumber = (int) (Math.pow(2,i-1)-1);
            while(prevTierNumber < tierNumber){
                if (treeNodes[prevTierNumber] != null){
                    if (prevTierNumber % 2 == 1){
                        treeNodes[prevTierNumber/2].left = treeNodes[prevTierNumber];
                    }else{
                        treeNodes[prevTierNumber/2-1].right = treeNodes[prevTierNumber];
                    }
                }
                prevTierNumber++;
            }
        }
        return treeNodes[0];
    }


    public String toString(){
        List<TreeNode> treeNodes = new ArrayList<>();
        treeNodes.add(this);
        return toArrayList(treeNodes).toString();
    }

    public List<Integer> toArrayList(List<TreeNode> list){
        List<Integer> res = new ArrayList<>();
        List<TreeNode> next = new ArrayList<>();
        boolean nextNonNullFlag = false;
        for (TreeNode treeNode : list) {
            if (treeNode != null){
                if (!nextNonNullFlag && (treeNode.left != null || treeNode.right != null))nextNonNullFlag = true;
                next.add(treeNode.left);
                next.add(treeNode.right);
                res.add(treeNode.val);
            }else{
                res.add(null);
            }
        }
        if (next.size() != 0 && nextNonNullFlag)res.addAll(toArrayList(next));
        return res;
    }

}
